#ifndef CLASS_NCTL_HASHMAPLIST
#define CLASS_NCTL_HASHMAPLIST

#include "Array.h"
#include "List.h"
#include "HashFunctions.h"

namespace nctl {

template <class K, class T, class HashFunc, bool IsConst> class HashMapListIterator;
template <class K, class T, class HashFunc, bool IsConst> struct HashMapListHelperTraits;
class String;

/// A template based hashmap implementation with separate chaining and list head cell
template <class K, class T, class HashFunc = FNV1aHashFunc<K>>
class HashMapList
{
  public:
	/// Iterator type
	using Iterator = HashMapListIterator<K, T, HashFunc, false>;
	/// Constant iterator type
	using ConstIterator = HashMapListIterator<K, T, HashFunc, true>;
	/// Reverse iterator type
	using ReverseIterator = nctl::ReverseIterator<Iterator>;
	/// Reverse constant iterator type
	using ConstReverseIterator = nctl::ReverseIterator<ConstIterator>;

	explicit HashMapList(unsigned int capacity);
	~HashMapList() { clear(); }

	/// Copy constructor
	HashMapList(const HashMapList &other);
	/// Move constructor
	HashMapList(HashMapList &&other);
	/// Copy-and-swap assignment operator
	HashMapList &operator=(HashMapList other);

	/// Swaps two hashmaps without copying their data
	inline void swap(HashMapList &first, HashMapList &second)
	{
		nctl::swap(first.buckets_, second.buckets_);
	}

	/// Returns an iterator to the first element
	Iterator begin();
	/// Returns a reverse iterator to the last element
	ReverseIterator rBegin();
	/// Returns an iterator to past the last element
	Iterator end();
	/// Returns a reverse iterator to prior the first element
	ReverseIterator rEnd();

	/// Returns a constant iterator to the first element
	ConstIterator begin() const;
	/// Returns a constant reverse iterator to the last element
	ConstReverseIterator rBegin() const;
	/// Returns a constant iterator to past the last lement
	ConstIterator end() const;
	/// Returns a constant reverse iterator to prior the first element
	ConstReverseIterator rEnd() const;

	/// Returns a constant iterator to the first element
	inline ConstIterator cBegin() const { return begin(); }
	/// Returns a constant reverse iterator to the last element
	inline ConstReverseIterator crBegin() const { return rBegin(); }
	/// Returns a constant iterator to past the last lement
	inline ConstIterator cEnd() const { return end(); }
	/// Returns a constant reverse iterator to prior the first element
	inline ConstReverseIterator crEnd() const { return rEnd(); }

	/// Subscript operator
	T &operator[](const K &key);
	/// Inserts an element if no other has the same key
	bool insert(const K &key, const T &value);
	/// Moves an element if no other has the same key
	bool insert(const K &key, T &&value);
	/// Constructs an element if no other has the same key
	template <typename... Args> bool emplace(const K &key, Args &&... args);

	/// Returns true if the hashmap is empty
	inline bool isEmpty() const { return size() == 0; }
	/// Returns the number of elements in the hashmap
	unsigned int size() const;
	/// Returns the average number of elements per bucket,
	inline float loadFactor() const { return size() / static_cast<float>(buckets_.size()); }
	/// Returns the number of buckets
	inline unsigned int bucketAmount() const { return buckets_.size(); }
	/// Returns the size of the bucket for the hash generated by the specified key
	inline unsigned int bucketSize(const K &key) const { return retrieveBucket(hashFunc_(key)).size(); }
	/// Returns the index of the bucket for the hash generated by the specified key
	inline unsigned int bucket(const K &key) const { return hashFunc_(key) % buckets_.size(); }
	/// Returns the hash of a given key
	inline hash_t hash(const K &key) const { return hashFunc_(key); }

	/// Clears the hashmap
	void clear();
	/// Checks whether an element is in the hashmap or not
	bool contains(const K &key, T &returnedValue) const;
	/// Checks whether an element is in the hashmap or not
	T *find(const K &key);
	/// Checks whether an element is in the hashmap or not (read-only)
	const T *find(const K &key) const;
	/// Removes a key from the hashmap, if it exists
	bool remove(const K &key);

	/// Sets the number of buckets to the new specified size and rehashes the container
	void rehash(unsigned int count);

  private:
	/// The template class for the node stored inside the hashmap
	class Node
	{
	  public:
		hash_t hash;
		K key;
		T value;

		Node()
		    : hash(NullHash) {}
		Node(hash_t hh, const K &kk)
		    : hash(hh), key(kk) {}
		Node(hash_t hh, const K &kk, const T &vv)
		    : hash(hh), key(kk), value(vv) {}
		Node(hash_t hh, const K &kk, T &&vv)
		    : hash(hh), key(kk), value(nctl::move(vv)) {}
		template <typename... Args>
		Node(hash_t hh, const K &kk, Args &&... args)
		    : hash(hh), key(kk), value(nctl::forward<Args>(args)...) {}
	};

	/// The bucket class for the hashmap, with separate chaining and list head cell
	class HashBucket
	{
	  public:
		HashBucket()
		    : size_(0) {}
		unsigned int size() const { return size_; }
		void clear();
		bool contains(hash_t hash, const K &key, T &returnedValue) const;
		T *find(hash_t hash, const K &key);
		const T *find(hash_t hash, const K &key) const;
		T &findOrInsert(hash_t hash, const K &key);
		bool insert(hash_t hash, const K &key, const T &value);
		bool insert(hash_t hash, const K &key, T &&value);
		template <typename... Args> bool emplace(hash_t hash, const K &key, Args &&... args);
		bool remove(hash_t hash, const K &key);

	  private:
		/// Number of nodes in this bucket
		unsigned int size_;
		/// Separate chaining with head cell
		Node firstNode_;
		/// Separate chaining with a linked list
		List<Node> collisionList_;

		Node *findNode(hash_t hash, const K &key);
		const Node *findNode(hash_t hash, const K &key) const;

		friend class HashMapListIterator<K, T, HashFunc, false>;
		friend class HashMapListIterator<K, T, HashFunc, true>;
		friend class HashMapList<K, T, HashFunc>;
	};

	Array<HashBucket> buckets_;
	HashFunc hashFunc_;

	HashBucket &retrieveBucket(hash_t hash);
	const HashBucket &retrieveBucket(hash_t hash) const;

	friend class HashMapListIterator<K, T, HashFunc, false>;
	friend class HashMapListIterator<K, T, HashFunc, true>;
	friend struct HashMapListHelperTraits<K, T, HashFunc, false>;
	friend struct HashMapListHelperTraits<K, T, HashFunc, true>;
};

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::Iterator HashMapList<K, T, HashFunc>::begin()
{
	Iterator iterator(this, Iterator::SentinelTagInit::BEGINNING);
	return ++iterator;
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::ReverseIterator HashMapList<K, T, HashFunc>::rBegin()
{
	Iterator iterator(this, Iterator::SentinelTagInit::END);
	return ReverseIterator(--iterator);
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::Iterator HashMapList<K, T, HashFunc>::end()
{
	return Iterator(this, Iterator::SentinelTagInit::END);
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::ReverseIterator HashMapList<K, T, HashFunc>::rEnd()
{
	Iterator iterator(this, Iterator::SentinelTagInit::BEGINNING);
	return ReverseIterator(iterator);
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::ConstIterator HashMapList<K, T, HashFunc>::begin() const
{
	ConstIterator iterator(this, ConstIterator::SentinelTagInit::BEGINNING);
	return ++iterator;
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::ConstReverseIterator HashMapList<K, T, HashFunc>::rBegin() const
{
	ConstIterator iterator(this, ConstIterator::SentinelTagInit::END);
	return ConstReverseIterator(--iterator);
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::ConstIterator HashMapList<K, T, HashFunc>::end() const
{
	return ConstIterator(this, ConstIterator::SentinelTagInit::END);
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::ConstReverseIterator HashMapList<K, T, HashFunc>::rEnd() const
{
	ConstIterator iterator(this, ConstIterator::SentinelTagInit::BEGINNING);
	return ConstReverseIterator(iterator);
}

template <class K, class T, class HashFunc>
void HashMapList<K, T, HashFunc>::HashBucket::clear()
{
	collisionList_.clear();
	size_ = 0;
}

template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::HashBucket::contains(hash_t hash, const K &key, T &returnedValue) const
{
	const Node *node = findNode(hash, key);

	if (node)
		returnedValue = node->value;

	return (node != nullptr);
}

template <class K, class T, class HashFunc>
T *HashMapList<K, T, HashFunc>::HashBucket::find(hash_t hash, const K &key)
{
	Node *node = findNode(hash, key);

	if (node)
		return &(node->value);

	return nullptr;
}

template <class K, class T, class HashFunc>
const T *HashMapList<K, T, HashFunc>::HashBucket::find(hash_t hash, const K &key) const
{
	const Node *node = findNode(hash, key);

	if (node)
		return &(node->value);

	return nullptr;
}

template <class K, class T, class HashFunc>
T &HashMapList<K, T, HashFunc>::HashBucket::findOrInsert(hash_t hash, const K &key)
{
	if (size_ == 0)
	{
		// Early-out if the bucket is empty
		firstNode_.hash = hash;
		firstNode_.key = key;
		size_++;
		return firstNode_.value;
	}

	Node *node = findNode(hash, key);
	if (node)
		return node->value;

	// The item has not been found, a new entry is created at the end of the list
	size_++;
	collisionList_.pushBack(Node(hash, key));
	return collisionList_.back().value;
}

template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::HashBucket::insert(hash_t hash, const K &key, const T &value)
{
	if (size_ == 0)
	{
		// Early-out if the bucket is empty
		firstNode_.hash = hash;
		firstNode_.key = key;
		firstNode_.value = value;
		size_++;
		return true;
	}

	Node *node = findNode(hash, key);
	if (node)
		return false;

	// The item has not been found, a new entry is created at the end of the list
	size_++;
	collisionList_.pushBack(Node(hash, key, value));
	return true;
}

template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::HashBucket::insert(hash_t hash, const K &key, T &&value)
{
	if (size_ == 0)
	{
		// Early-out if the bucket is empty
		firstNode_.hash = hash;
		firstNode_.key = key;
		firstNode_.value = nctl::move(value);
		size_++;
		return true;
	}

	Node *node = findNode(hash, key);
	if (node)
		return false;

	// The item has not been found, a new entry is created at the end of the list
	size_++;
	collisionList_.pushBack(Node(hash, key, nctl::move(value)));
	return true;
}

template <class K, class T, class HashFunc>
template <typename... Args>
bool HashMapList<K, T, HashFunc>::HashBucket::emplace(hash_t hash, const K &key, Args &&... args)
{
	if (size_ == 0)
	{
		// Early-out if the bucket is empty
		firstNode_.hash = hash;
		firstNode_.key = key;
		new (&firstNode_.value) T(nctl::forward<Args>(args)...);
		size_++;
		return true;
	}

	Node *node = findNode(hash, key);
	if (node)
		return false;

	// The item has not been found, a new entry is created at the end of the list
	size_++;
	collisionList_.emplaceBack(hash, key, nctl::forward<Args>(args)...);
	return true;
}

/*! \return True if the element has been found and removed */
template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::HashBucket::remove(hash_t hash, const K &key)
{
	// Early-out if the bucket is empty
	if (size_ == 0)
		return false;

	bool found = false;
	if (firstNode_.hash == hash && firstNode_.key == key)
	{
		// The item has been found in the direct access node
		found = true;

		// Bring the first element of the list, if any, as direct access node
		if (collisionList_.isEmpty() == false)
		{
			firstNode_ = collisionList_.front();
			collisionList_.popFront();
		}
		size_--;
	}
	else
	{
		for (typename List<Node>::ConstIterator i = collisionList_.begin(); i != collisionList_.end(); ++i)
		{
			if ((*i).hash == hash && (*i).key == key)
			{
				// The item has been found in the list
				found = true;
				i = collisionList_.erase(i);
				size_--;

				// The item has been removed and the iterator is no longer valid
				break;
			}
		}
	}

	return found;
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::Node *HashMapList<K, T, HashFunc>::HashBucket::findNode(hash_t hash, const K &key)
{
	if (size_ == 0)
		return nullptr;

	if (firstNode_.hash == hash && firstNode_.key == key)
		// The item has been found in the direct access node
		return &firstNode_;
	else
	{
		for (typename List<Node>::Iterator i = collisionList_.begin(); i != collisionList_.end(); ++i)
		{
			// The item has been found in the list
			if ((*i).hash == hash && (*i).key == key)
				return &(*i);
		}
	}

	return nullptr;
}

template <class K, class T, class HashFunc>
const typename HashMapList<K, T, HashFunc>::Node *HashMapList<K, T, HashFunc>::HashBucket::findNode(hash_t hash, const K &key) const
{
	if (size_ == 0)
		return nullptr;

	if (firstNode_.hash == hash && firstNode_.key == key)
		// The item has been found in the direct access node
		return &firstNode_;
	else
	{
		for (typename List<Node>::ConstIterator i = collisionList_.begin(); i != collisionList_.end(); ++i)
		{
			// The item has been found in the list
			if ((*i).hash == hash && (*i).key == key)
				return &(*i);
		}
	}

	return nullptr;
}

template <class K, class T, class HashFunc>
HashMapList<K, T, HashFunc>::HashMapList(unsigned int capacity)
    : buckets_(capacity, ArrayMode::FIXED_CAPACITY)
{
	FATAL_ASSERT_MSG(capacity > 0, "Zero is not a valid capacity");

	for (unsigned int i = 0; i < capacity; i++)
		buckets_[i] = HashBucket();
}

template <class K, class T, class HashFunc>
HashMapList<K, T, HashFunc>::HashMapList(const HashMapList<K, T, HashFunc> &other)
    : buckets_(other.buckets_)
{
}

template <class K, class T, class HashFunc>
HashMapList<K, T, HashFunc>::HashMapList(HashMapList<K, T, HashFunc> &&other)
    : buckets_(nctl::move(other.buckets_))
{
}

/*! \note The parameter should be passed by value for the idiom to work. */
template <class K, class T, class HashFunc>
HashMapList<K, T, HashFunc> &HashMapList<K, T, HashFunc>::operator=(HashMapList<K, T, HashFunc> other)
{
	swap(*this, other);
	return *this;
}

template <class K, class T, class HashFunc>
T &HashMapList<K, T, HashFunc>::operator[](const K &key)
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).findOrInsert(hash, key);
}

/*! \return True if the element has been inserted */
template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::insert(const K &key, const T &value)
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).insert(hash, key, value);
}

/*! \return True if the element has been inserted */
template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::insert(const K &key, T &&value)
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).insert(hash, key, nctl::move(value));
}

/*! \return True if the element has been emplaced */
template <class K, class T, class HashFunc>
template <typename... Args>
bool HashMapList<K, T, HashFunc>::emplace(const K &key, Args &&... args)
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).emplace(hash, key, nctl::forward<Args>(args)...);
}

template <class K, class T, class HashFunc>
unsigned int HashMapList<K, T, HashFunc>::size() const
{
	unsigned int totalSize = 0;
	for (unsigned int i = 0; i < buckets_.size(); i++)
		totalSize += buckets_[i].size();

	return totalSize;
}

template <class K, class T, class HashFunc>
void HashMapList<K, T, HashFunc>::clear()
{
	for (unsigned int i = 0; i < buckets_.size(); i++)
		buckets_[i].clear();
}

template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::contains(const K &key, T &returnedValue) const
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).contains(hash, key, returnedValue);
}

/*! \note Prefer this method if copying `T` is expensive, but always check the validity of returned pointer. */
template <class K, class T, class HashFunc>
T *HashMapList<K, T, HashFunc>::find(const K &key)
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).find(hash, key);
}

/*! \note Prefer this method if copying `T` is expensive, but always check the validity of returned pointer. */
template <class K, class T, class HashFunc>
const T *HashMapList<K, T, HashFunc>::find(const K &key) const
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).find(hash, key);
}

template <class K, class T, class HashFunc>
bool HashMapList<K, T, HashFunc>::remove(const K &key)
{
	const hash_t hash = hashFunc_(key);
	return retrieveBucket(hash).remove(hash, key);
}

template <class K, class T, class HashFunc>
void HashMapList<K, T, HashFunc>::rehash(unsigned int count)
{
	const unsigned int totalSize = size();
	if (totalSize == 0 || count < totalSize)
		return;

	HashMapList<K, T, HashFunc> hashMap(count);

	unsigned int bucketIndex = 0;
	HashBucket &bucket = buckets_[bucketIndex];
	while (bucketIndex < buckets_.size() - 1)
	{
		while (bucketIndex < buckets_.size() - 1 && bucket.size() == 0)
			bucket = buckets_[++bucketIndex];

		if (bucket.size() > 0)
		{
			hashMap[bucket.firstNode_.key] = bucket.firstNode_.value;
			for (typename List<Node>::ConstIterator i = bucket.collisionList_.begin(); i != bucket.collisionList_.end(); ++i)
				hashMap[(*i).key] = (*i).value;

			++bucketIndex;
		}
	}

	*this = nctl::move(hashMap);
}

template <class K, class T, class HashFunc>
typename HashMapList<K, T, HashFunc>::HashBucket &HashMapList<K, T, HashFunc>::retrieveBucket(hash_t hash)
{
	const unsigned int index = hash % buckets_.size();
	return buckets_[index];
}

template <class K, class T, class HashFunc>
const typename HashMapList<K, T, HashFunc>::HashBucket &HashMapList<K, T, HashFunc>::retrieveBucket(hash_t hash) const
{
	const unsigned int index = hash % buckets_.size();
	return buckets_[index];
}

template <class T>
using StringHashMapList = HashMapList<String, T, FNV1aFuncHashContainer<String>>;

}

#endif
